package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no29;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.divide(-2147483648, -1));
    }

    public int divide(int dividend, int divisor) {
        if (divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            if (dividend == Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            return -dividend;
        }
        boolean less0 = true;
        long dividendL = dividend;
        long divisorL = divisor;
        if (dividendL < 0) {
            dividendL = -dividendL;
            if (divisorL < 0) {
                less0 = false;
                divisorL = -divisorL;
            }
        } else {
            if (divisorL < 0) {
                divisorL = -divisorL;
            } else {
                less0 = false;
            }
        }
        long result = tryFind(dividendL, divisorL);
        if (less0) {
            result = -result;
        }
        return result >= Integer.MIN_VALUE &&
                result <= Integer.MAX_VALUE ? (int) result : Integer.MAX_VALUE;
    }

    public long tryFind(long dividend, long divisor) {
        if (dividend < divisor) {
            return 0;
        }
        long plus = 1;
        long temp = divisor;
        while ((temp <<= 1) < dividend) {
            plus <<= 1;
        }
        return plus + tryFind(dividend - (temp >> 1), divisor);
    }
}
